package targetToOffer.nintehDay;

import java.util.LinkedList;

/**
 * @author Godc
 * @description
 */
public class ValidateStackSequences {
    public static void main(String[] args) {
        ValidateStackSequencesSolution s = new ValidateStackSequencesSolution();
        boolean b = s.validateStackSequences(new int[]{1,2,3,4,5}, new int[]{4,5,3,2,1});
        System.out.println(b);
    }
}
class ValidateStackSequencesSolution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
//        if(popped==null||pushed==null) return false;
//        LinkedList<Integer> stack = new LinkedList<>();
//        int j = 0;
//        for(int i = 0;i<pushed.length;i++){
//            stack.push(pushed[i]);
//            while(j<popped.length&&!stack.isEmpty()&&stack.peek()==popped[j]){
//                stack.pop();
//                j++;
//            }
//        }
//        return stack.isEmpty();
        if(pushed.length==0||popped.length==0) return false;
        LinkedList<Integer> stack = new LinkedList<>();
        int j = 0;
        for(int i = 0;i<pushed.length;i++){
            stack.push(pushed[i]);
            while(!stack.isEmpty()&&j<popped.length&&stack.peek()==popped[j]){
                stack.pop();
                j++;
            }
        }
        return stack.isEmpty();
    }
}